//#define _CRT_SECURE_NO_WARNINGS 1
//#include "iostream"
//#include <list>
//#include <vector>
//#include <stack>
//class MinStack {
//public:
//    MinStack() {
//
//    }
//
//    void push(int val) {
//        v.push(val);
//        if (small.empty() || val <= small.top())
//            small.push(val);
//
//    }
//
//    void pop() {
//        if (v.empty())
//            return;
//
//        if (v.top() == small.top())
//            small.pop();
//        v.pop();
//
//    }
//
//    int top() {
//        return v.top();
//    }
//
//    int getMin() {
//        return small.top();
//    }
//private:
//    std::stack<int> v;
//    std::stack<int> small;
//
//};
//
//class Solution {
//public:
//    bool isPalindrome(ListNode* head) {
//        vector<int> arr;
//        ListNode* ptr = head;
//        while (ptr != nullptr)
//        {
//            arr.push_back(ptr->val);
//            ptr = ptr->next;
//        }
//        int end = arr.size() - 1;
//        int begin = 0;
//        while (begin < end)
//        {
//            if (arr[begin++] != arr[end--])
//            {
//                return false;
//            }
//        }
//        return true;
//
//    }
//};
//
//bool SamTree(TreeNode* root, TreeNode* subRoot)
//{
//    if (root == nullptr && subRoot == nullptr)
//        return true;
//    if (root == nullptr || subRoot == nullptr)
//        return false;
//    if (root->val != subRoot->val)
//        return false;
//    return SamTree(root->left, subRoot->left) && SamTree(root->right, subRoot->right);
//}
//class Solution {
//public:
//    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
//        if (root == nullptr)
//            return false;
//        if (root->val == subRoot->val)
//            if (SamTree(root, subRoot))
//                return true;
//        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//    }
//};
//
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> vv;
//        if (root == nullptr)
//            return vv;
//        queue<TreeNode*> ret;
//        ret.push(root);
//        while (!ret.empty())
//        {
//            vector<int> tmp;
//            int n = ret.size();
//            while (n--)
//            {
//                TreeNode* node = ret.front();
//                ret.pop();
//                tmp.push_back(node->val);
//                if (node->left)
//                    ret.push(node->left);
//                if (node->right)
//                    ret.push(node->right);
//            }
//            vv.push_back(tmp);
//        }
//        return vv;
//
//    }
//};
